#include <vector>
#include <stack>
using namespace std;
/*
 * @lc app=leetcode.cn id=84 lang=cpp
 *
 * [84] 柱状图中最大的矩形
 */

// @lc code=start
class Solution {
public:
    // 暴力法
    // int largestRectangleArea(vector<int>& heights) {
    //     int res = 0;
    //     for (int i = 0; i < heights.size(); i++) {
    //         int l = i, r = i;
    //         while (l >= 0 && heights[l] >= heights[i]) l--;
    //         while (r < heights.size() && heights[r] >= heights[i]) r++;
    //         res = max(res, (r - l - 1) * heights[i]);
    //     }
    //     return res;
    // }

    // 单调栈
    int largestRectangleArea(vector<int>& heights) {
        stack<int> single; int res = 0;
        for (int i = 0; i < heights.size(); i++) {
            if (single.empty()) {
                single.push(i); continue;
            }
            while (!single.empty() && heights[single.top()] > heights[i]) {
                int now = heights[single.top()], l = -1;
                single.pop();
                if (!single.empty()) l = single.top();
                int len = i - l - 1;
                res = max(res, now * len);
            }
            single.push(i);
        }
        while (!single.empty()) {
            int n = single.top(); single.pop(); int l = -1;
            if (!single.empty()) l = single.top();
            int len = heights.size() - l - 1;
            res = max(res, heights[n] * len);
        }
        return res;
    }
};
// @lc code=end

